/*
算法构思：

暴力正向算法

目标：
遍历每个数组中元素，找出该元素作为起始位的和最大的连续子数组，比较后输出最大和

步骤：
1. 定义一个最大和变量，每次跟任意子数组比较

缺点：
O(n2)效率过低，不能通过，显示执行时间过长

*/
public class Solution_1 {
    public int maxSubArray(int[] nums) {
        //存储最大和的变量
        int max=nums[0];
        //子数组的和
        int sum=0;
        //遍历任所有子数组
        for(int i=0;i<nums.length;i++){
            //最初，任意索引开始位置，第一个子数组的和就是该索引位本身的值
            sum=nums[i];
            //是否更改Max的值
            if(sum>max)
            {
                max=sum;
            }
            //计算该索引位开始的其他子数组的和
            for(int j=i+1;j<nums.length;j++)
            {
                sum+=nums[j];
                if(sum>max)
                {
                    max=sum;
                }
            }
        }
        //返回最大值
        return max;
    }
}
